// https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/

// 算法思路总结：
// 1. 中序遍历寻找二叉搜索树第k小元素
// 2. 利用BST中序遍历有序的特性
// 3. 全局计数器记录剩余查找次数
// 4. 找到第k个节点时记录结果并提前返回
// 5. 时间复杂度：O(k)，空间复杂度：O(h)（递归栈深度）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    int count;
    int ret;
    int kthSmallest(TreeNode* root, int k) 
    {
        count = k;
        dfs(root);
        
        return ret;
    }

    void dfs(TreeNode* root)
    {
        if (count == 0)
            return ;
        if (root == nullptr) 
            return ;

        dfs(root->left);

        count--;
        if (count == 0)
            ret = root->val;

        dfs(root->right);
    }
};

int main()
{
    int k1 = 1, k2 = 3;
    vector<string> tree1 = {"3", "1", "4", "null", "2"};
    vector<string> tree2 = {"5", "3", "6", "2", "4", "null", "null", "1"};

    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    cout << sol.kthSmallest(root1, k1) << endl;
    cout << sol.kthSmallest(root2, k2) << endl;

    return 0;
}